const AVLTree = require("../template")

function testAVLTreeDeletion() {
  console.log(
    "1. 删除叶子节点测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      avl.insert(50)
      avl.insert(30)
      avl.insert(70)
      avl.insert(20)
      avl.insert(40)
      
      // 删除叶子节点
      avl.delete(20)
      avl.delete(40)
      
      return avl.search(20) === null &&
             avl.search(40) === null &&
             avl.search(50) !== null &&
             avl.search(30) !== null &&
             avl.search(70) !== null &&
             avl.isValid() === true
    })()
  )

  console.log(
    "2. 删除只有一个子节点的节点测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据构造只有一个子节点的情况
      avl.insert(50)
      avl.insert(30)
      avl.insert(70)
      avl.insert(20)
      
      // 删除只有一个子节点的节点
      avl.delete(30)
      
      return avl.search(30) === null &&
             avl.search(50) !== null &&
             avl.search(70) !== null &&
             avl.search(20) !== null &&
             avl.isValid() === true
    })()
  )

  console.log(
    "3. 删除有两个子节点的节点测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      avl.insert(50)
      avl.insert(30)
      avl.insert(70)
      avl.insert(20)
      avl.insert(40)
      avl.insert(60)
      avl.insert(80)
      
      // 删除有两个子节点的节点
      avl.delete(50)
      
      return avl.search(50) === null &&
             avl.search(30) !== null &&
             avl.search(70) !== null &&
             avl.search(20) !== null &&
             avl.search(40) !== null &&
             avl.search(60) !== null &&
             avl.search(80) !== null &&
             avl.isValid() === true
    })()
  )

  console.log(
    "4. 删除根节点测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      avl.insert(50)
      avl.insert(30)
      avl.insert(70)
      
      // 删除根节点
      avl.delete(50)
      
      return avl.search(50) === null &&
             avl.search(30) !== null &&
             avl.search(70) !== null &&
             avl.isValid() === true
    })()
  )

  console.log(
    "5. 删除后中序遍历测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      const values = [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45]
      values.forEach(val => avl.insert(val))
      
      // 删除一些节点
      avl.delete(30)
      avl.delete(70)
      avl.delete(10)
      
      // 获取中序遍历结果
      const inorder = avl.inorder()
      const remainingValues = values.filter(val => ![30, 70, 10].includes(val))
      const expected = remainingValues.sort((a, b) => a - b)
      
      return JSON.stringify(inorder) === JSON.stringify(expected) &&
             avl.isValid() === true
    })()
  )

  console.log(
    "6. 删除后最小最大值测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      const values = [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45]
      values.forEach(val => avl.insert(val))
      
      // 删除最小值和最大值
      avl.delete(10) // 最小值
      avl.delete(80) // 最大值
      
      const min = avl.getMin()
      const max = avl.getMax()
      const remainingValues = values.filter(val => ![10, 80].includes(val))
      const expectedMin = Math.min(...remainingValues)
      const expectedMax = Math.max(...remainingValues)
      
      return min === expectedMin &&
             max === expectedMax &&
             avl.isValid() === true
    })()
  )

  console.log(
    "7. 删除后树高度测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      const values = [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45]
      values.forEach(val => avl.insert(val))
      
      const initialHeight = avl.getHeight()
      
      // 删除一些节点
      avl.delete(30)
      avl.delete(70)
      avl.delete(10)
      
      const finalHeight = avl.getHeight()
      const finalSize = avl.getSize()
      
      // 删除后高度应该合理
      const maxHeight = Math.ceil(Math.log2(finalSize + 1))
      
      return finalHeight <= maxHeight &&
             finalHeight > 0 &&
             avl.isValid() === true
    })()
  )

  console.log(
    "8. 删除不存在的节点测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      avl.insert(50)
      avl.insert(30)
      avl.insert(70)
      
      // 尝试删除不存在的节点
      avl.delete(100)
      avl.delete(5)
      
      // 验证树结构没有改变
      return avl.search(50) !== null &&
             avl.search(30) !== null &&
             avl.search(70) !== null &&
             avl.search(100) === null &&
             avl.search(5) === null &&
             avl.getSize() === 3 &&
             avl.isValid() === true
    })()
  )

  console.log(
    "9. 批量删除测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      const values = [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 55, 65, 75, 85]
      values.forEach(val => avl.insert(val))
      
      // 批量删除
      const toDelete = [30, 70, 10, 25, 35, 45]
      toDelete.forEach(val => avl.delete(val))
      
      // 验证删除结果
      const deletedCorrect = toDelete.every(val => avl.search(val) === null)
      const remainingCorrect = values.filter(val => !toDelete.includes(val))
        .every(val => avl.search(val) !== null)
      
      return deletedCorrect &&
             remainingCorrect &&
             avl.getSize() === values.length - toDelete.length &&
             avl.isValid() === true
    })()
  )

  console.log(
    "10. this上下文删除测试:",
    (() => {
      const deletionObj = {
        multiplier: 2,
        processDeletion: function(values, toDelete) {
          const avl = new AVLTree()
          values.forEach(val => avl.insert(val))
          toDelete.forEach(val => avl.delete(val))
          return avl.getSize() * this.multiplier
        }
      }
      
      const values = [10, 20, 30, 40, 50]
      const toDelete = [20, 40]
      return deletionObj.processDeletion(values, toDelete) === 6 // 3*2=6
    })()
  )

  console.log(
    "11. 复杂对象this绑定删除测试:",
    (() => {
      const deletionConfigObj = {
        config: { threshold: 2 },
        processWithConfig: function(values, toDelete) {
          const avl = new AVLTree()
          values.forEach(val => avl.insert(val))
          toDelete.forEach(val => avl.delete(val))
          return avl.getSize() >= this.config.threshold
        }
      }
      
      const values = [10, 20, 30, 40, 50]
      const toDelete = [10, 50]
      return deletionConfigObj.processWithConfig(values, toDelete) === true
    })()
  )

  console.log(
    "12. 删除后重新插入测试:",
    (() => {
      const avl = new AVLTree()
      
      // 插入数据
      const values = [50, 30, 70, 20, 40, 60, 80]
      values.forEach(val => avl.insert(val))
      
      // 删除一些节点
      avl.delete(30)
      avl.delete(70)
      
      // 重新插入相同的值
      avl.insert(30)
      avl.insert(70)
      
      // 验证所有值都存在
      const allFound = values.every(val => avl.search(val) !== null)
      
      return allFound &&
             avl.getSize() === values.length &&
             avl.isValid() === true
    })()
  )
}

testAVLTreeDeletion()
